Graph / Interval graph (Bibtex)

P273: Enumeration of all interval supergraph that contains a given graph

Input:

A graph $G = (V, E)$.

Output:

All interval supergraphs each of which contain $G$.

Complexity:

$O(|V|^3)$ time for each and $O(|V|^2)$ space.

Comment:

Reference:

[Kiyomi2006a] (Bibtex)

P274: Enumeration of all interval graph of a given graph

Input:

A graph $G = (V, E)$.

Output:

All interval graphs of $G$.

Complexity:

$O((|V|+|E|)^2)$ time for each.

Comment:

Reference:

[Kiyomi2006a] (Bibtex)

P123: Enumeration of Proper Interval Graphs

Input:

An integer $n$.

Output:

All proper interval graphs with $n$ vertices.

Complexity:

$O(1)$ time per proper interval graph and $O(n)$ space, after $O(n^2)$ preprocessing time.

Comment:

Preprocessing: generating the complete graph with $n$ vertices.

Reference:

[Saitoh2010a] (Bibtex)